import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public static List<Integer> getRow(int rowIndex) {
        List<Integer> prev = new ArrayList<>();

        for(int i = 0; i <= rowIndex; i++){
            List<Integer> cur = new ArrayList<>();
            for(int j = 0; j <= i; ++j){
                if(j == 0 || j == i){
                    cur.add(1);
                }else{
                    cur.add(prev.get(j) + prev.get(j - 1));
                }
            }
            prev = cur;
        }
        return prev;
    }

    public static int minimumTotal1(List<List<Integer>> triangle) {
        int n = triangle.size(), INF = 0x3f3f3f3f;
        int[][] dp = new int[n + 1][n + 1];
        for(int i = 0; i <= n; i++){
            dp[i][0] = INF;
        }
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j <= n; j++){
                dp[i][j] = INF;
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i - 1).get(j - 1);
            }
        }

        int ret = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++){
            ret = Math.min(ret, dp[n][j]);
        }
        return ret;
    }
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);

        for(int i = 1; i < n; i++){
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for(int j = 1; j < i; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int ret = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            ret = Math.min(ret, dp[n - 1][i]);
        }
        return ret;
    }

    public int maxProfit1(int[] prices) {
        int n = prices.length;
        int min = prices[0], ret = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            int tmp = prices[i] - min;
            min = Math.min(min, prices[i]);
            ret = Math.max(ret, tmp);
        }
        return ret;
    }

    public int maxProfit2(int[] prices) {
        int n = prices.length;

        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = -prices[0];
        int ret = 0;
        for(int i = 1; i < n; i++){
            f[i] = Math.max(f[i - 1], g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + prices[i]);
            ret = Math.max(f[i], g[i]);
        }
        return ret;
    }

    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        for(int j = 0; j < 3; j++){
            f[0][j] = -0x3f3f3f3f;
            g[0][j] = -0x3f3f3f3f;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < 3; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int ret = 0;
        for(int j = 0; j < 3; j++){
            ret = Math.max(ret, g[n - 1][j]);
        }
        return ret;
    }

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }

    public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n){
        if(n == 1){
            c.add(a.remove(a.size() - 1));
            return ;
        }
        dfs(a, c, b, n - 1);
        c.add(a.remove(a.size() - 1));
        dfs(b, a, c, n - 1);
    }

//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        if(list1 == null) { return list2;}
//        if(list2 == null) { return list1;}
//
//        if(list1.val <= list2.val){
//            list1.next = mergeTwoLists(list1.next, list2);
//            return list1;
//        }else{
//            list2.next = mergeTwoLists(list2.next, list1);
//            return list2;
//        }
//    }

//    public ListNode swapPairs(ListNode head) {
//        if(head == null || head.next == null) { return head;}
//
//        ListNode tmp = swapPairs(head.next.next);
//        ListNode ret = head.next;
//        ret.next = head;
//        head.next = tmp;
//        return ret;
//    }


    public static void main(String[] args) {
        System.out.println(getRow(3));
//        Integer[][] x = new Integer[][]{{2},{3,4},{6,5,7},{4,1,8,3}}
//        List<List<Integer>> list = Arrays.asList(x);
//        System.out.println(minimumTotal());
    }
}